﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp1
{
    public class Solution21
    {
        public int MinPathSum(int[][] grid)
        {
            //交错数组的赋值方式
            int gridLength = grid.Length ;
            int[][] ans = new int[gridLength][];
            //先赋值横行
            for (int i = 0; i < ans.Length; i++)
            {
                //赋值纵行
                ans[i] = new int[grid[0].Length];
            }
            int ansLength = ans[0].Length - 1;
            for (int i = 0; i < grid.Length; i++)
            {
                for (int j = 0; j < grid[0].Length; j++)
                {
                    if (i == 0 && j == 0)
                    {
                        ans[i][j] = grid[i][j];
                    }
                    else
                    {
                        if (i == 0)
                        {
                            ans[i][j] = ans[i][j - 1] + grid[i][j];
                        }
                        else if (j == 0)
                        {
                            ans[i][j] = ans[i - 1][j] + grid[i][j];
                        }
                        else
                        {
                            ans[i][j] = Math.Min(ans[i][j - 1] + grid[i][j], ans[i - 1][j] + grid[i][j]);
                        }
                    }
                }
            }
            return ans[gridLength -1][ansLength];
        }
    }
}
